package dynamicProgramming.review11_15;

public class Class718 {
    //TODO:2023/11/15 求最长公共子数组
//TODO:2023/11/15 dp[i][j] ：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j]。 （特别注意： “以下标i - 1为结尾的A” 标明一定是 以A[i-1]为结尾的字符串 ）

    public int findLength(int[] nums1, int[] nums2) {

        //TODO:2023/11/15根据dp[i][j]的定义，dp[i][j]的状态只能由dp[i - 1][j - 1]推导出来。
        //
        //即当A[i - 1] 和B[j - 1]相等的时候，dp[i][j] = dp[i - 1][j - 1] + 1;
        //
        //根据递推公式可以看出，遍历i 和 j 要从1开始！
        int m = nums1.length;
        int n = nums2.length;
        int[][] dp=new int[m+1][n+1];
        int ans=0;
        for (int i = 1; i <=m ; i++) {
            for (int j = 1; j <=n ; j++) {
                if (nums1[i-1]==nums2[j-1]){
                    dp[i][j]=dp[i-1][j-1]+1;
                }
                ans=Math.max(ans,dp[i][j]);

            }
        }
        return  ans;

    }

}
